// Package day_03_linklist has_cycle_lc_141_easy
// @Title day_03_linklist
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/8/30 17:34
// @Create  2021/8/30 17:34
package day_03_linklist

import "fmt"

// HasCycleUseSet 判断链表有没有环 集合解法  O(N)
func HasCycleUseSet(head *ListNode) bool {
	if head == nil {
		return false
	}
	var hashMap = make(map[*ListNode]bool, 0)
	for head != nil {
		key, ok := hashMap[head]
		fmt.Println(key, ok)
		if ok {
			return true
		} else {
			hashMap[head] = true
		}
		head = head.Next
	}
	return false
}

// HasCycleUseTwoPoint 判断链表有没有环 双指针解法 O(N)
func HasCycleUseTwoPoint(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	slow, fast := head, head.Next
	for true {
		if fast == nil || fast.Next == nil {
			break
		}
		slow, fast = slow.Next, fast.Next.Next
		if fast == slow {
			return true
		}
	}
	return false
}
